

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        A = [head]
        while A[-1].next:
            A.append(A[-1].next)
        return A[len(A)//2]
    '''
    复杂度分析
    时间复杂度：O(N)，其中 N 是给定链表中的结点数目
    空间复杂度：O(N)，即数组 A 用去的空间。
    '''
    def middleNode2(self, head: Optional[ListNode]) -> Optional[ListNode]:
        n,cur = 0 ,head
        while cur:
            n +=1
            cur=cur.next
        k,cur=0,head
        while k<n//2:
            k+=1
            cur = cur.next
        return cur
    '''
    复杂度分析
    时间复杂度：O(N)，即数组 A 用去的空间。
    空间复杂度：O(1)，即数组 A 用去的空间。
    '''

    def middleNode3(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast =head
        while fast and fast.next:
            slow=  slow.next
            fast = fast.next.next
        return slow
    '''
    复杂度分析
    时间复杂度：O(N)，其中 N 是给定链表的结点数目。
    空间复杂度：O(1)，只需要常数空间存放 slow 和 fast 两个指针。
    '''













